//
// Created by Administrator on 2021/6/12.
//

/*
给你一个整数数组cost和一个整数target。请你返回满足如下规则可以得到的最大整数：

给当前结果添加一个数位（i + 1）的成本为cost[i]（cost数组下标从 0 开始）。
总成本必须恰好等于target。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 "0" 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    string largestNumber(vector<int> &cost, int target) {
        /**
         * dp[i+1][j] 表示使用前 i个数位且花费总成本恰好为 j 时的最大位数，
         * 若花费总成本无法为 j，则规定其为 −∞。特别地，dp[0][] 为不选任何数位的状态，
         * 因此除了dp[0][0] 为 0，其余 dp[0][j] 全为 −∞。
         */
        vector<vector<int>> dp(10, vector<int>(target + 1, INT_MIN)); // 二维dp数组
        vector<vector<int>> from(10, vector<int>(target + 1)); // 记录从哪里变化而来
        dp[0][0] = 0;
        for (int i = 0; i < 9; ++i) {
            int c = cost[i]; // 这一位的成本
            for (int j = 0; j <= target; ++j) { // 遍历目标
                if (j < c) { // 无法选第i位数
                    dp[i + 1][j] = dp[i][j];
                    from[i + 1][j] = j;
                } else {
                    if (dp[i][j] > dp[i + 1][j - c] + 1) {
                        dp[i + 1][j] = dp[i][j];
                        from[i + 1][j] = j;
                    } else {
                        dp[i + 1][j] = dp[i + 1][j - c] + 1;
                        from[i + 1][j] = j - c;
                    }
                }
            }
        }
        if (dp[9][target] < 0) {
            return "0";
        }
        string ans;
        int i = 9, j = target;
        while (i > 0) {
            if (j == from[i][j]) {
                --i;
            } else {
                ans += char('0' + i);
                j = from[i][j];
            }
        }
        return ans;
    }
};

class Solution2 {
public:
    string largestNumber(vector<int> &cost, int target) {
        vector<int> dp(target + 1, INT_MIN);
        dp[0] = 0;
        // 一维dp数组
        // dp得到凑出target的最多位数
        for (int c : cost) {
            for (int j = c; j <= target; ++j) {
                dp[j] = max(dp[j], dp[j - c] + 1);
            }
        }
        if (dp[target] < 0) {// 位数<0,无结果
            return "0";
        }
        string ans;
        // 遍历数位 从后往前 得到的较大
        for (int i = 8, j = target; i >= 0; i--) {
            for (int c = cost[i]; j >= c && dp[j] == dp[j - c] + 1; j -= c) {
                ans += char('1' + i);
            }
        }
        return ans;
    }
};


int main() {
    vector<int> cost{4, 3, 2, 5, 6, 7, 2, 5, 5};
    vector<int> cost2{7, 6, 5, 5, 5, 6, 8, 7, 8};
    Solution2 sol;
    cout << sol.largestNumber(cost, 9) << endl;
    cout << sol.largestNumber(cost2, 12) << endl;
    return 0;
}